using System.Collections.Generic;
using Kopernikus.Collections.Generic;
using Kopernikus.Parsing.LR;
using Kopernikus.Parsing.Utility;

namespace Kopernikus.Parsing.Earley
{
    public abstract class EarleyDFA
    {
        public const int InvalidState = -1;

        private readonly List<Set<Production>> m_completed = new List<Set<Production>>();
        private readonly Dictionary<Pair<Symbol, int>, int> m_goto = new Dictionary<Pair<Symbol, int>, int>();
        private readonly IGrammar m_grammar;
        private readonly Dictionary<Set<LR0Item>, int> m_set2state = new Dictionary<Set<LR0Item>, int>();
        private readonly List<Set<LR0Item>> m_stateSets = new List<Set<LR0Item>>();

        public EarleyDFA(IGrammar grammar)
        {
            m_grammar = grammar;
        }

        public IGrammar Grammar
        {
            get { return m_grammar; }
        }

        protected List<Set<LR0Item>> StateSets
        {
            get { return m_stateSets; }
        }

        public virtual int GetGoto(int state, Symbol s)
        {
            int gotoState;
            return m_goto.TryGetValue(new Pair<Symbol, int>(s, state), out gotoState) ? gotoState : InvalidState;
        }

        protected virtual bool TryGetGoto(int state, Symbol s, out int gotoState)
        {
            return m_goto.TryGetValue(new Pair<Symbol, int>(s, state), out gotoState);
        }

        protected void DefineGoto(int state, Symbol symbol, int gotoState)
        {
            if (state != InvalidState)
            {
                m_goto[new Pair<Symbol, int>(symbol, state)] = gotoState;
            }
        }

        protected static Set<LR0Item> AdvanceStateItems(Symbol symbol, Set<LR0Item> stateSet)
        {
            Set<LR0Item> gotoSet = new Set<LR0Item>();
            foreach (LR0Item item in stateSet)
            {
                if (!item.IsComplete)
                {
                    if (item.DotSymbol.Equals(symbol))
                    {
                        gotoSet.Add(item.AdvanceDot());
                    }
                }
            }
            return gotoSet;
        }

        protected Set<LR0Item> GetClosure(Set<LR0Item> kernel)
        {
            Set<LR0Item> closure = new Set<LR0Item>();
            if (kernel.Count == 0)
            {
                return closure;
            }

            WorkList<Symbol> workList = new WorkList<Symbol>(false);
            foreach (LR0Item item in kernel)
            {
                if (!item.IsComplete)
                {
                    workList.Enqueue(item.DotSymbol);
                }
            }
            if (workList.Count == 0)
            {
                return closure;
            }

            Symbol s;
            while (workList.Dequeue(out s))
            {
                foreach (Production p in Grammar.ProductionSets.GetProductionsByLHS(s))
                {
                    LR0Item newItem = closure.Add(new LR0Item(p, 0));
                    if (!newItem.IsComplete)
                    {
                        workList.Enqueue(newItem.DotSymbol);
                    }
                }
            }
            return closure;
        }

        public Set<LR0Item> GetStateSet(int state)
        {
            return m_stateSets[state];
        }


        public Set<Production> Completed(int state)
        {
            return m_completed[state];
        }

        protected int AddStateSet(Set<LR0Item> set)
        {
            if (set.Count == 0)
            {
                return InvalidState;
            }

            int state;
            if (!m_set2state.TryGetValue(set, out state))
            {
                state = StateSets.Count;
                m_set2state.Add(set, state);
                StateSets.Add(set);

                Set<Production> completed = new Set<Production>();
                foreach (LR0Item item in set)
                {
                    if (item.IsComplete)
                    {
                        completed.Add(item.Production);
                    }
                }
                m_completed.Add(completed);
            }
            return state;
        }

        public virtual int Build()
        {
            Set<LR0Item> initialItems = new Set<LR0Item>();
            foreach (Production production in m_grammar.StartProductions)
            {
                initialItems.Add(new LR0Item(production, 0));
            }
            return AddStateSet(initialItems);
        }

        public IEnumerable<int> GetStatesContaining(LR0Item item)
        {
            for (int i = 0; i < m_stateSets.Count; ++i)
            {
                if (m_stateSets[i].Contains(item))
                {
                    yield return i;
                }
            }
        }
    }
}